import copy
from collections import defaultdict


class Solution:
    def maxDistance(self, s: str, k: int) -> int:
        count = defaultdict(int)
        max_distance = 0
        kc = k

        def getMaxElem(d):
            max_key = 'W'
            for key in ('S', 'N', 'E'):
                if d[key] > d[max_key]:
                    max_key = key
            return max_key

        for t in s:
            count[t] += 1
            k = kc
            # 对于 NS
            count_copy = copy.copy(count)
            max_key = getMaxElem(count_copy)
            if count_copy['S'] < count_copy['N']:
                r = min(count_copy['S'], k)
                count_copy['S'] -= r
                count_copy[max_key] += r
                k -= r
            else:
                r = min(count_copy['N'], k)
                count_copy['N'] -= r
                count_copy[max_key] += r
                k -= r
            if count_copy['W'] < count_copy['E']:
                r = min(count_copy['W'], k)
                count_copy['W'] -= r
                count_copy[max_key] += r
                k -= r
            else:
                r = min(count_copy['E'], k)
                count_copy['E'] -= r
                count_copy[max_key] += r
                k -= r
            max_distance = max(max_distance,
                               abs(count_copy['N'] - count_copy['S']) + abs(count_copy['W'] - count_copy['E']))
        return max_distance


if __name__ == '__main__':
    s = Solution()
    r = s.maxDistance("NWSE", 1)
    print(r)
